SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Hybrid algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Hybrid algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>A <b>hybrid algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> that combines two or more other algorithms that solve the same problem, either choosing one based on some characteristic of the data, or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>"Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, hybrid algorithms are very common in optimized real-world implementations of <a href="Recursive_algorithm" class="mw-redirect" title="Recursive algorithm">recursive algorithms</a>, particularly <a href="Divide-and-conquer_algorithm#Implementation_issues" title="Divide-and-conquer algorithm">implementations</a> of

<a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">divide-and-conquer</a> or <a href="Decrease-and-conquer" class="mw-redirect" title="Decrease-and-conquer">decrease-and-conquer</a> algorithms, where the size of the data decreases as one moves deeper in the recursion. In this case, one algorithm is used for the overall approach (on large data), but deep in the recursion, it switches to a different algorithm, which is more efficient on small data. A common example is in <a href="Sorting_algorithm" title="Sorting algorithm">sorting algorithms</a>, where the insertion sort, which is inefficient on large data, but very efficient on small data (say, five to ten elements), is used as the final step, after primarily applying another algorithm, such as <a href="Merge_sort" title="Merge sort">merge sort</a> or <a href="Quicksort" title="Quicksort">quicksort</a>. Merge sort and quicksort are asymptotically optimal on large data, but the overhead becomes significant if applying them to small data, hence the use of a different algorithm at the end of the recursion. A highly optimized hybrid sorting algorithm is <a href="Timsort" title="Timsort">Timsort</a>, which combines merge sort, insertion sort, together with additional logic (including <a href="Binary_search" title="Binary search">binary search</a>) in the merging logic.

</p><p>A general procedure for a simple hybrid recursive algorithm is <i>short-circuiting the base case,</i> also known as <i><a href="Arm's-length_recursion" class="mw-redirect" title="Arm's-length recursion">arm's-length recursion</a>.</i> In this case whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking if it is null, checking null before recursing. This is useful for efficiency when the algorithm usually encounters the base case many times, as in many tree algorithms, but is otherwise considered poor style, particularly in academia, due to the added complexity.

</p><p>Another example of hybrid algorithms for performance reasons are <a href="Introsort" title="Introsort">introsort</a> and <a href="Introselect" title="Introselect">introselect</a>, which combine one algorithm for fast average performance, falling back on another algorithm to ensure (asymptotically) optimal worst-case performance. Introsort begins with a <a href="Quicksort" title="Quicksort">quicksort</a>, but switches to a <a href="Heap_sort" class="mw-redirect" title="Heap sort">heap sort</a> if quicksort is not progressing well; analogously introselect begins with <a href="Quickselect" title="Quickselect">quickselect</a>, but switches to <a href="Median_of_medians" title="Median of medians">median of medians</a> if quickselect is not progressing well.

</p><p>Centralized <a href="Distributed_algorithm" title="Distributed algorithm">distributed algorithms</a> can often be considered as hybrid algorithms, consisting of an individual algorithm (run on each distributed processor), and a combining algorithm (run on a centralized distributor) – these correspond respectively to running the entire algorithm on one processor, or running the entire computation on the distributor, combining trivial results (a one-element data set from each processor). A basic example of these algorithms are <a href="Distribution_sort" class="mw-redirect" title="Distribution sort">distribution sorts</a>, particularly used for <a href="External_sorting" title="External sorting">external sorting</a>, which divide the data into separate subsets, sort the subsets, and then combine the subsets into totally sorted data; examples include <a href="Bucket_sort" title="Bucket sort">bucket sort</a> and <a href="Flashsort" title="Flashsort">flashsort</a>.

</p><p>However, in general distributed algorithms need not be hybrid algorithms, as individual algorithms or combining or communication algorithms may be solving different problems. For example, in models such as <a href="MapReduce" title="MapReduce">MapReduce</a>, the Map and Reduce step solve different problems, and are combined to solve a different, third problem.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMalekGuruswamyOwensPandya1989" class="citation book cs1">Malek, Miroslaw; Guruswamy, Mohan; Owens, Howard; Pandya, Mihir (1989). <i>A hybrid algorithm technique</i>. University of Texas at Austin, Department of Computer Sciences.</cite></span>

</li>

</ol></div></div>

<ul><li><a href="Hybrid_algorithm_(constraint_satisfaction)" title="Hybrid algorithm (constraint satisfaction)">Hybrid algorithm (constraint satisfaction)</a></li>

<li><a href="Hybrid_genetic_algorithm" class="mw-redirect" title="Hybrid genetic algorithm">Hybrid genetic algorithm</a></li>

<li><a href="Hybrid_input_output_(HIO)_algorithm_for_phase_retrieval" class="mw-redirect" title="Hybrid input output (HIO) algorithm for phase retrieval">Hybrid input output (HIO) algorithm for phase retrieval</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-10" href="https://en.wikipedia.org/wiki/?title=Hybrid_algorithm&oldid=1299835564">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>